/**
 *  @file .
 *  @author wangxiaowei <wangxiaowei0303@163.com>
 *  @date 2015-02-11-13.20
 */

#include <bits/stl_tree.h>

namespace mystd{

/**
 *  获取节点 x 的后继.
 *  使用的算法可以参考算法导论/二叉搜索树/后继算法,只不过这里
 *  对于每一个节点,其父节点都不为0,根节点的父节点指向着一个哨兵,
 *  哨兵的 _M_parent,_M_left,_M_right 属性为 0.
 *  当 x 不存在后继时,就返回哨兵.
 *  TODO,关于哨兵这里是我自己猜测的,需要验证.
 */
static _Rb_tree_node_base*
local_Rb_tree_increment(_Rb_tree_node_base *x){
	if(x->_M_right != 0)
		x = _Rb_tree_node_base::_S_minimum(x->_M_right);
	else{
		_Rb_tree_node_base *y = x->_M_parent;
		while(y->_M_right == x){
			x = y;
			y = y->_M_parent;
		}
		// 当循环终止时,要么 y->_M_left == x,此时 y 就是 x 的后继;
		// 要么 y 是哨兵,此时 _M_left==_M_right==0,此时也返回 y.
		x = y;
	}
	return x;
}

_Rb_tree_node_base*
_Rb_tree_increment(_Rb_tree_node_base *x){
	return local_Rb_tree_increment(x);
}

const _Rb_tree_node_base*
_Rb_tree_increment(const _Rb_tree_node_base *x){
	return local_Rb_tree_increment(
		const_cast<_Rb_tree_node_base*>(x)
	);
}



};
